import sys

class Solution(object):
    def __init__(self):
        self.dp = None
    def coinChange(self, coins, amount):
        self.dp = [sys.maxsize] * (amount + 1)
        self.dp[0] = 0
        for i in range(len(self.dp)):
            if self.dp[i] == sys.maxsize:
                continue
            for coin in coins:
                next = i + coin
                if next <= amount:
                    self.dp[next] = min(self.dp[next], self.dp[i] + 1)
        if self.dp[amount] == sys.maxsize:
            return -1
        else:
            return self.dp[amount]

s = Solution()
data = [333,364,408,118,63,270,69,111,218,371,305]
print(s.coinChange(data, 5615))